﻿#pragma once

// 请完成哈希表的如下操作
// 哈希函数采用除留余数法﻿
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 哈希表中支持字符串的操作
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 131;
			hash += e;
		}

		return hash;
	}
};

// 以下采用开放定址法，即线性探测解决冲突
namespace W_open_address
{
	enum State
	{
		EXIST,
		EMPTY,
		DELETE

	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		bool Insert(const pair<K, V>& kv) {
			if (Find(kv.first)) {
				return false;
			}
			if (_n * 10 / _tables.size() >= 7) {
				HashTable<K, V, Hash> tmp;
				tmp._tables.resize(_tables.size() * 2);
				for (size_t i = 0; i < _tables.size(); i++) {
					if (_tables[i]._state == EXIST) {
						tmp.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(tmp._tables);
			}
			Hash hs;
			size_t ky = hs(kv.first);
			ky = ky % _tables.size();
			while (_tables[ky]._state == EXIST) {
				ky++;
				ky = ky % _tables.size();
			}
			_tables[ky]._kv = kv;
			_tables[ky]._state = EXIST;
			_n++;
			return true;
		}
		HashData<K, V>* Find(const K& key) {
			Hash hs;
			size_t ky = hs(key) % _tables.size();
			size_t start = (ky - 1) % _tables.size();
			while (start != ky) {
				if (_tables[ky]._state == EMPTY) {
					return nullptr;
				}
				if (_tables[ky]._state == EXIST &&
					_tables[ky]._kv.first == key) {
					return &_tables[ky];
				}
				ky++;
				ky %= _tables.size();
			}
			return nullptr;
		}
		bool Erase(const K& key) {
			HashData<K, V>* hd = Find(key);
			Hash hs;
			if (hd) {
				hd->_state = DELETE;
				_n--;
				return true;
			}
			return false;
		}

		void Print() {
			for (auto& e : _tables) {
				if (e._state == DELETE) {
					cout << "  ";
				}
				else {
					cout << e._kv.second << " ";
				}
			}
			cout << endl;
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;  // 表中存储数据个数
	};
}


// 实现完成后，请对整形 和 字符串完成测试

